package com.cuz.daileetcode.bat100;

import com.cuz.daileetcode.前序中序后序Morris.All;
import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.HashMap;

public class 字符串不同字面子序列的种数 {


    public static int solution1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int mod = (int) (Math.pow(10,9) + 7);
        HashMap<Character, Integer> map = new HashMap<>((int) ((26 / 0.75) + 1));
        int all = 1;
        for (int i = 0; i < s.length(); i++) {
            //当前字符
            char x = s.charAt(i);
            int newAdd = all;
            int curAll = all;
            curAll = (curAll + newAdd) % mod;
            curAll = (curAll - (map.containsKey(x) ? map.get(x) : 0) + mod) % mod;
            all = curAll;
            map.put(x, newAdd);
        }
        return all - 1;
    }

    public static void main(String[] args) {
        String abc = "adbae";
        System.out.println(solution1(abc));
        System.out.println(solution(abc));
    }

    private static int solution(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int mod = 10 ^ 9 + 7;
        HashMap<Character, Integer> memoryPreAddCount = new HashMap<>((int) ((26 / 0.75) + 1));
        int ans = 1;
        for (int i = 0; i < s.length(); i++) {
            //当前字符
            char curChar = s.charAt(i);
            int newAdd = ans;
            ans = newAdd + ans - memoryPreAddCount.getOrDefault(curChar, 0);
            memoryPreAddCount.put(curChar, newAdd);
        }
        return ans - 1;
    }


}
